package com.example.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长回文子串
 * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的
 * 回文串
 * 的长度。
 * <p>
 * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
 * <p>
 * 输入:s = "abccccdd"
 * 输出:7
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 */
public class Leetcode409 {
    // left right 中间往两边比较
    public int longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        // 统计每个字符出现的次数
        Map<Character, Integer> map = new HashMap<>();
        for (char c : chars) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int res = 0;
        int odd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Integer v = entry.getValue();
            if (v % 2 != 0) {
                // 如果是奇数 只能那偶数个（v-1）构成新的回文串
                res += v - 1;
                // 多余的一个可以放中间 因此长度+1
                odd = 1;
            } else {
                // 如果是偶数个 一定可以构成新的回文串 ，长度+v
                res += v;

            }

        }
        return res + odd;
    }

    public static void main(String[] args) {
        int i = new Leetcode409().longestPalindrome("abccccdd");
        System.out.println(i);
    }
}
